package com.example.question.dp.dp2;

/**
 * 打家劫舍二  这个有环
 */
public class Code03_213 {
    public static void main(String[] args) {
        Code03_213 code = new Code03_213();
        int rob = code.rob(new int[]{1});
        System.out.println(rob);

    }


    public int rob(int[] nums) {
        int len = nums.length;
        // 一个元素的时候下面得递归处理不了
        if (len == 1) {
            return nums[0];
        }
        int num1 = dfs(nums, 0, len - 1, new Integer[len]);
        int num2 = dfs(nums, 1, len, new Integer[len]);
        return Math.max(num1, num2);
    }

    private int dfs(int[] nums, int startIndex, int endIndex, Integer[] dp) {
        if (startIndex == endIndex - 1) {
            return nums[startIndex];
        }
        if (startIndex >= endIndex) {
            return 0;
        }

        if (dp[startIndex] != null) {
            return dp[startIndex];
        }

        int num1 = dfs(nums, startIndex + 1, endIndex, dp);
        int num2 = dfs(nums, startIndex + 2, endIndex, dp);
        int max = Math.max(num1, num2 + nums[startIndex]);
        dp[startIndex] = max;
        return max;
    }

}
